In existing virtual memory systems, the virtual and physical memory in use by a process is defined by a working set list, and mapped by a tree-structured page table. When the address space of a process is "swapped out" to free up physical memory, the page table page itself must be swapped out as well. Tear down and recreation of page tables as a result of swapping in existing systems can be an expensive operation involving multiple traversals of the working set list. This is the case because the hierarchical organization of the page table is not reflected in the working set list.
Further in existing systems, a swapper process executes as shared system code within an operating system. The swapper process removes other processes from main memory. When the swapper process removes a process from main memory, it prepares the memory used by the process, including the memory used by the process to store the page table for that process, to be written to secondary storage, for example a magnetic disc.
In one example existing system, the swapper process builds a "swap map" representing the physical memory used by the process to be out-swapped so that the physical memory may be used by another process. The working set list is the structure which drives execution of the swapper process in existing systems. The swap file is a file in secondary storage that contains all out-swapped processes. Each outswapped process consumes one swap slot within the swap file. The act of writing contents of the physical memory used by a process to be outswapped and related information into a swap map is referred to as a process "out-swap". An input/output subsystem subsequently copies the code and data from the physical memory indicated by the swap map to secondary storage. At that point the physical memory of the outswapped process may be used by another process.
As the size of virtual addresses grow, and the amount of physical memory used by a typical process increases, the expense of using traditional systems to outswap a process having a hierarchical page table structure becomes prohibitive. Costs associated with traversing the working set list in order to tear down the page table of a process to be outswapped, and then to rebuild the page table upon in-swap are especially exorbitant.
Accordingly for the reasons stated above there is required a new system for swapping a process in and out of memory. The new system should conveniently and efficiently store and restore a hierarchical page table data structure to and from secondary storage. The new system should further eliminate multiple traversals of a working set list during outswap or in-swap of a process.